สารานุกรมออนไลน์ | Siam Wiki
ไม่เจอคำค้นที่ต้องการ
หน้าแรก
ความต่อเนื่อง (ทฤษฎีกราฟ)
หน้าแรก
ความต่อเนื่อง (ทฤษฎีกราฟ)
ใน
คณิตศาสตร์
และ
วิทยาการคอมพิวเตอร์
เรื่อง
ทฤษฎีกราฟ
ความต่อเนื่อง
หรือ
ความเชื่อมโยง
(
อังกฤษ
: Connectivity) เป็นคุณสมบัติหนึ่งของ
กราฟ
โดย
กราฟต่อเนื่อง
หรือ
กราฟเชื่อมโยง
(Connected graph) หมายความว่ากราฟไม่ขาดจากกัน กล่าวคือ สำหรับทุกๆสอง
จุดยอด
ใดๆ จะสามารถไปถึงกันได้ หรือก็คือมี
วิถี
ระหว่างจุดยอดทั้งสอง ในขณะที่
กราฟไม่ต่อเนื่อง
หรือ
กราฟไม่เชื่อมโยง
(Unconnected graph) หมายความว่ากราฟนั้นขาดออกจากกัน กล่าวคือมีอย่างน้อยสองจุดยอด ที่ไม่สามารถไปถึงกันได้ หรือก็คือไม่มีวิถีระหว่างจุดยอดทั้งสองจุดนั้นความต่อเนื่องของกราฟ ยังสามารถมองได้ในอีกแง่มุมหนึ่ง คือจำนวนของจุดยอดหรือเส้นเชื่อมที่น้อยที่สุด ที่ถ้าลบจุดยอดหรือเส้นเชื่อมเหล่านั้นทิ้งแล้ว กราฟดังกล่าวจะกลายเป็นกราฟไม่ต่อเนื่อง
[1]
จะเห็นว่าความต่อเนื่องของกราฟนั้นบ่งบอกถึงความแข็งแกร่ง/ความทนทานของกราฟ ตัวอย่างเช่นหากพิจารณาให้บ้านเป็นจุดยอด และการเดินสายไฟระหว่างบ้านเป็นเส้นเชื่อม หากกราฟดังกล่าวมีความต่อเนื่องมาก (นั่นคือต้องลบจำนวนจุดยอดหรือเส้นเชื่อมมาก) ก็หมายความว่าถึงแม้จะมีสายไฟบางเส้นเสียไป ทั้งหมู่บ้านก็ยังมีไฟฟ้าใช้อยู่ ในขณะที่หากกราฟดังกล่าวมีความต่อเนื่องน้อย ก็หมายความว่าสายไฟบางเส้นเสียไป อาจทำให้บางบ้านไม่มีไฟฟ้าใช้ปัญหา
การไหลในเครือข่าย
มีความเกี่ยวข้องกับเรื่องความต่อเนื่องของกราฟเป็นอย่างมาก
เมนูนำทาง
ความต่อเนื่อง (ทฤษฎีกราฟ)
นิยามต่างๆ
อ้างอิง
Menger's theorem
ใกล้เคียง
ความต่อเนื่อง (ทฤษฎีกราฟ)
แหล่งที่มา
WikiPedia: ความต่อเนื่อง (ทฤษฎีกราฟ)
http://diestel-graph-theory.com/GrTh.html
×